1. Field of the Invention
This invention relates to built-in self-test programmable logic arrays. Accordingly, it is a general object of this invention to provide new and improved arrays of such character.
2. General Background
The introduction of LSI/VLSI technology (i.e., large scale integration/very large scale integration) has increased the difficulty of both the designing and the testing of complex systems which can be implemented on a semiconductor chip. The programmable nature of programmable logic arrays (PLA) makes the design task much easier. A small complex system, an IBM 7441 Buffered Terminal Control Unit using PLAs, is described by J. C. Logue, N. F. Brickman, F. Howley, J. W. Jones, and W. W. Wu, "Hardware Implementation of a Small System in Programmable Logic Arrays", IBM J. Research Development, pp. 110-119, March 1975, which suggests that the PLA approach exploits many of the benefits of LSI/VLSI without high engineering design cost. Due to the regular structure, PLA implementation of both combinational circuits and finite state machines can be easily automated. For example, in GTE Corporation's SILC (tm) silicon compiler, PLAs with feedback paths are used to implement the control logic for each generalized finite state machine, as reported by C. P. Rosebrugh and J. H. Vellenga, "Circuit Synthesis for the Silc Silicon Compiler", IEEE 1985 Custom Integrated Circuits Conference, pp. 384-388, May 1985. In addition to making circuit design easier, due to the array-oriented structures, the PLA approach for LSI/VLSI also simplifies the testing problem.
A review of the following papers,
D. L. Ostapko and S. J. Hong, "Fault Analysis and Test Generation for PLAs", IEEE Transactions on Computers, Vol. C-28, September 1979, PA0 J. E. Smith, "Detection of Faults in PLAs", IEEE Transactions on Computers. Vol. C-28, November 1979, PA0 Pradis Bose and J. A. Abraham, "Functional Testing of PLAs", 19th Design Automation Conference, August 1982, and PA0 R.-S. Wei and A. Sangiovanni-Vincentelli, "PLATYPUS: A PLA Test Pattern Generation Tool", 22nd D.A. Conference, June 1985, PA0 K. A. Hua, J.-Y. Jou, and J. A. Abraham, "Built-In Tests for VLSI Finite-State Machine", Proceedings FTCS-14; PA0 R. Treuer, H. Fujiwara, and V. K. Agarwal, "Implementing a Built-in Self-Test PLA Design", IEEE Design and Test of Computers, April 1985; PA0 S. Z. Hassan and E. J. McCluskey, "Testing PLAs Using Multiple Parallel Signature Analyzers", Proceedings FTCS-13; and PA0 W. Daehn and J. Mucha, "A Hardware Approach to Self-Testing of Large Programmable Logic Arrays", IEEE Transactions on Computers, Vol. C-30, November, 1981, pp. 829-833.
indicates that much effort has been directed to the problem of fault detection in the PLAs in recent years. However, the testing of large PLAs is difficult. Pseudorandom number sequences as discussed by D. K. Bhavsar and R. W. Heckelman, "Self-testing by Polynomial Division", Proceedings of the IEEE International Test Conference, pp. 208-216, 1981, are attractive in many testing problems; unfortunately, they are not an effective approach for PLA testing due to the high fan-in in PLAs, as indicated by T. W. Williams and K. P. Porker, "Design for Testability: A Survey", IEEE Transactions on Computers, Vol, C-31, No. 1, pp. 2-15, January 1982. Due to the structural regularity of PLAs, this test problem has attracted tremendous attention in recent years. In particular, the design of built-in self-test (BIST) PLAs with low overhead and high fault coverage appears to be a possible solution to the testing problem.
Under the BIST approach, the logic required to generate tests for a circuit, and the logic required for analysis of the circuit's response to those tests, are implemented in hardware residing within the same system as the circuit under test. Thus, the circuit is capable of testing itself and reporting to its environment whether it is a working circuit or not.
Various built-in self-test programmable logic arrays (BIST PLAs) have been discussed in the literature, including
These literature suggestions offer different degrees of testability, have different properties, require different hardware overhead, and have different degrees of performance impact due to additional circuitry. BIST designs are clearly a worthwhile approach, but like many other design decisions, involve tradeoffs and are not inexpensive.
The most critical requirement for designing a BIST PLA is that the test patterns used to test the PLA should be simple, that only a mere modification or augmentation of an existing circuit would serve as a test pattern generator in a testing mode. That is, the overhead for test logic should be kept as small as possible. The size of test patterns should be small so that the test pattern can be quickly generated. An output response should be compressible into a small number of bits. The technique used for data compression should have several attributes. It must be simple enough for implementation as part of a BIST scheme to reduce overhead. It must be fast enough to remove it as a limiting factor in testing-time. It must not lose the error information contained in the output response stream of a faulty PLA. Following, four prior art BIST PLA designs are discussed. The advantage and disadvantage of each design in terms of hardware overhead, numbers of test patterns, and delay per test applications are also discussed.